Vào năm 1527, Mạc Đăng Dung người Hải Dương cướp ngôi Nhà Lê, lập nên Nhà Mạc, lấy niên hiệu Minh Đức. Lúc ấy con cháu các công thần đời trước phát xuất từ Thanh Hóa không phục, liên tiếp khởi binh chống lại. Hữu vệ Điện tiền tướng quân An Thành hầu Nguyễn Kim, con cháu một gia đình vọng tộc lớn đã nhiều đời làm quan Nhà Lê, bèn lánh sang Ai Lao, tụ tập binh mã, mưu tính việc khôi phục Nhà Lê. Đến năm 1533, Nguyễn Kim lập con trai của Hoàng đế Lê Chiêu Tông lên ngôi, tức Hoàng đế Lê Trang Tông. Trang Tông phong Nguyễn Kim là Thái sư Hưng quốc công.[7][8][9]. Thế Nam Bắc triều hình thành.

Khi mới đầu Nguyễn Kim đóng đồn ở Mường Sùng thuộc Ai Lao[6]. Trịnh Kiểm đến đầu quân cho Nguyễn Kim, được phong làm Tri Mã cơ, tước Dực Nghĩa hầu. Là người có tài, ông được Nguyễn Kim giao cho nhiều trọng trách và gả con gái là Ngọc Bảo cho[10]. Theo Lịch sử vương quốc Đàng Ngoài của Alexandre De Rhodes: Khi quân Mạc tấn công vào kinh thành, quân Nguyễn Kim bị vây giữa vòng vây của địch. Kim đã giao ước với các tướng rằng ông sẽ gả con gái cho ai có thể giải cứu ông và nghĩa quân ra khỏi vòng vây ấy. Trịnh Kiểm phi ngựa xông lên hăng hái đánh giết giặc, cứu được Kim và mở đường huyết lộ cho nghĩa quân rút lui. Vì vậy, theo lời hứa, Nguyễn Kim gả con gái là Ngọc Bảo cho Kiểm và giao nhiều trọng trách cho ông, đặc biệt là việc huấn luyện kị binh cho nghĩa quân. Theo sách Đại Việt thông sử, Trịnh Kiểm có sức khỏe và tài lược hơn người, theo Nguyễn Kim đi đánh dẹp khắp nơi, lập nhiều chiến công, được Nguyễn Kim gả con gái cho.[11]

Năm 1539, ông được Hoàng đế Lê Trang Tông phong làm Đại tướng quân, tước Dực Quận Công[12][13] do có công cầm binh mã sang Ai Lao đón Lê Trang Tông (vua Lê thấy Kiểm dung mạo tuấn tú nên phong tước cho ông, lúc đó ông 37 tuổi). Hoàng đế cũng coi ông là một đại tướng tâm phúc, ban ấn tướng quân, quản lĩnh quân giao chiến với Nhà Mạc ở các vùng Thanh Hoa, thắng quân Mạc ở Lôi Dương[14].

Năm 1540, Thái sư Hưng quốc công Nguyễn Kim dẫn quân về Nghệ An, thanh thế lẫy lừng, đến đâu là gần xa đều hàng phục. Năm sau, Mạc Đăng Dung chết, quân Nguyễn Kim tiến về đánh Thanh Hóa, Nghệ An, đến năm 1543, thu phục được thành Tây Đô (Thanh Hóa).

Đến năm 1545, Lê Trang Tông thân chinh đánh Mạc, đóng bản doanh ở hạt Yên Mô (Ninh Bình ngày nay) tướng cũ của Nhà Mạc là Trung Hậu hầu Dương Chấp Nhất đầu độc chết Thái sư Nguyễn Kim.[15] Trước khi chết, Nguyễn Kim giao lại toàn bộ binh mã cho Trịnh Kiểm[10]. Toàn bộ binh quyền của Nhà Lê rơi vào tay Trịnh Kiểm. Tháng 8 âm lịch năm này, vua Bắc triều Mạc Phúc Hải sai Thái tể Ninh quốc công Mạc Phúc Tư dùng quân ngũ phủ và các trấn đánh úp bản doanh của Lê Trang Tông. Khi quân Mạc tới sông Phù Chẩn, Trang Tông đích thân ra đánh, Dực quận công Trịnh Kiểm làm Đề thống ngự doanh, dẫn quân tiên phong phá tan quân Mạc. Quân Mạc chết hại vô số, Ninh quốc công phải trốn về Bắc. Cùng năm, Trịnh Kiểm được hoàng đế phong làm Đô tướng tiết chế các dinh quân thuỷ bộ các xứ kiêm tổng nội ngoại bình chương quân quốc trọng sự, hàm Thái sư, tước Lượng quốc công[16]. Lượng quốc công Trịnh Kiểm quyết định mọi công việc trong nước, bao gồm cả việc bổ nhiệm quan lại rồi mới tâu vua sau[17].